#define DEBUG
#include <cstdio>

using namespace std;

const int maxn=50, mods=10000;

class Matrix {
public:
  int n, m, a[maxn+1][maxn+1];

  void init(int n, int m, const int a[][maxn+1]) {
    this->n = n, this->m = m;
    for (int i=0; i<n; i++) {
      for (int j=0; j<m; j++) {
	this->a[i][j] = a[i][j];
      }
    }
  }
};

void mul(const Matrix *a, const Matrix *b, Matrix *c) {
  if (a->m!=b->n) {
    throw -1;
  }
  c->n=a->n, c->m=b->m;
  for (int i=0; i<a->n; i++) {
    for (int j=0; j<b->m; j++) {
      c->a[i][j]=0;
      for (int k=0; k<a->m; k++) {
	c->a[i][j] = (c->a[i][j]+a->a[i][k]*b->a[k][j]%mods)%mods;
      }
    }
  }
}

void power(Matrix *a, long long n) {
  static Matrix temp[2], s[2];
  temp[0].init(a->n, a->m, a->a);
  s[0].n=a->n, s[0].m=a->m;
  for (int i=0; i<a->n; i++) {
    s[0].a[i][i]=1;
  }
  int i, j;
  for (i=0, j=0; n>1; n/=2) {
    if (n%2) {
      j++;
      mul(&s[(j-1)%2], &temp[i%2], &s[j%2]);
    }
    i++;
    mul(&temp[(i-1)%2], &temp[(i-1)%2], &temp[i%2]);
  }
  mul(&temp[i%2], &s[j%2], a);
}

int main() {
#ifdef DEBUG
  freopen("1.in", "r", stdin);
  freopen("1.out", "w", stdout);
#endif

  static int map[maxn+1][maxn+1];
  static Matrix move[12];
  int n, m, start, end, nfish;
  long long k;
  scanf("%d %d %d %d %lld", &n, &m, &start, &end, &k);
  for (int i=1; i<=m; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    map[x][y]=1;
    map[y][x]=1;
  }

  for (int i=0; i<12; i++) {
    move[i].init(n, n, map);
  }

  scanf("%d", &nfish);
  for (int i=1; i<=nfish; i++) {
    int t, p[4];
    scanf("%d", &t);
    for (int j=0; j<t; j++) {
      scanf("%d", p+j);
    }
    for (int j=0; j<12; j++) {
      for (int k=0; k<n; k++) {
	move[j].a[k][p[j%t]]=0;
      }
    }
  }

  static Matrix ans[2], temp[2];
  ans[0].n=1, ans[0].m=n;
  ans[0].a[0][start]=1;
  if (k>12) {
    temp[1].init(move[1].n, move[1].m, move[1].a);
    for (int i=2; i<=12; i++) {
      mul(&temp[(i-1)%2], &move[i%12], &temp[i%2]);
    }
    power(&temp[0], k/12);
    mul(&ans[0], &temp[0], &temp[1]);
    ans[0].init(temp[1].n, temp[1].m, temp[1].a);
  }
  for (int i=1; i<=k%12; i++) {
    mul(&ans[(i-1)%2], &move[i], &ans[i%2]);
  }
  printf("%d", ans[k%2].a[0][end]);

  fclose(stdin);
  fclose(stdout);
  return 0;
}
